package labuladong.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class _95_UniqueBinarySearchTreesIi {

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class Solution {
        /* 主函数 */
        public List<TreeNode> generateTrees(int n) {
            if (n == 0) return new LinkedList<>();
            // 构造闭区间 [1, n] 组成的 BST
            return build(1, n);
        }

        /* 构造闭区间 [lo, hi] 组成的 BST */
        List<TreeNode> build(int lo, int hi) {
            List<TreeNode> res = new LinkedList<>();
            // base case
            if (lo > hi) {
                res.add(null);
                return res;
            }

            // 1、穷举 root 节点的所有可能。
            for (int i = lo; i <= hi; i++) {
                // 2、递归构造出左右子树的所有合法 BST。
                List<TreeNode> leftTree = build(lo, i - 1);
                List<TreeNode> rightTree = build(i + 1, hi);
                // 3、给 root 节点穷举所有左右子树的组合。
                for (TreeNode left : leftTree) {
                    for (TreeNode right : rightTree) {
                        // i 作为根节点 root 的值
                        TreeNode root = new TreeNode(i);
                        root.left = left;
                        root.right = right;
                        res.add(root);
                    }
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void printTreeNode(TreeNode root, List<String> list) {
        if (root == null) {
            list.add("null");
            return;
        }
        // 以下为整型转字符串的三种方式
        list.add(root.val + "");
//        list.add(Integer.toString(root.val));
//        list.add(String.valueOf(root.val));

        if (root.left != null || root.right != null) {  //非叶子节点
            printTreeNode(root.left, list);
            printTreeNode(root.right, list);
        }
    }

    // 输入一棵二叉树的根节点，层序遍历这棵二叉树
    static List levelTraverse(TreeNode root, List<String> list) {
        if (root == null) return null;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        int depth = 1;
        // 从上到下遍历二叉树的每一层
        while (!q.isEmpty()) {
            int sz = q.size();
            // 从左到右遍历每一层的每个节点
            for (int i = 0; i < sz; i++) {
                TreeNode cur = q.poll();
                list.add(cur.val + "");

                if (cur.left != null) {
                    q.offer(cur.left);
                }
                if (cur.right != null) {
                    q.offer(cur.right);
                }
            }
            depth++;
        }
        return list;
    }

    public static void main(String[] args) {
        Solution solution = new _95_UniqueBinarySearchTreesIi().new Solution();
        List<TreeNode> treeNodes = solution.generateTrees(3);
        for (TreeNode treeNode : treeNodes) {
            List<String> list = new ArrayList<>();

//            printTreeNode(treeNode, list);
//            System.out.println(Arrays.toString(list.toArray()));

            List res = levelTraverse(treeNode, list);
            System.out.println(res);
        }
    }
}
